#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<stack>
#include<vector>
#include<unordered_map>
#include<algorithm>

using namespace std;


bool isValid(string s) {
    stack<char> stk;
    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] == ')')
        {
            if (stk.empty() || stk.top() != '(')
                return false;
            stk.pop();
        }
        else if (s[i] == '}')
        {
            if (stk.empty() || stk.top() != '{')
                return false;
            stk.pop();
        }
        else if (s[i] == ']')
        {
            if (stk.empty() || stk.top() != '[')
                return false;
            stk.pop();
        }
        else 
            stk.push(s[i]);
    }
    if (!stk.empty())
        return false;
    return true;
}

int minimumSum(vector<int>& nums) {
    int count = 0, res = INT_MAX;
    int leftmin = nums[0];

    auto findright = [&](int i) {
        int tmp = i + 1;
        int res = INT_MAX;
        while (tmp < nums.size())
        {
            if (nums[tmp] < nums[i])
                res = min(nums[tmp], res);
            tmp++;
        }
        return res;
    };
    
    int right = findright(1);
    for(int i = 1;i<nums.size()-1;i++)
    {
        if (nums[i] > nums[i - 1] && right == INT_MAX || right == nums[i])
            right = findright(i);

        if (right == INT_MAX)
        {
            leftmin = min(nums[i], leftmin);
            continue;
        }

        if(leftmin < nums[i])
            if (leftmin + right + nums[i] < res)
                res = leftmin + right + nums[i];

        leftmin = min(nums[i], leftmin);

    }
    if (res == INT_MAX)
        return -1;
    return res;
}

int minGroupsForValidAssignment(vector<int>& nums) {
    unordered_map<int, int> um;
    for (int i = 0; i < nums.size(); i++)
    {
        um[nums[i]]++;
    }

    int nmin = INT_MAX;
    for (auto it : um)
        nmin = min(nmin, it.second);

    bool flag = false;
    int res = 0;
    for (auto it : um)
        if (it.second >= nmin + 1)
        {
            int tmp = it.second % (nmin + 1);
            if (tmp < nmin && tmp != 0 || flag)
            {
                if (it.second % nmin)
                {
                    res += it.second / nmin + 1;
                    flag = true;
                }
                else 
                    res += it.second / nmin;
            }
            else
            {
                if (tmp)
                    res += it.second / (nmin + 1) + 1;
                else
                    res += it.second / (nmin + 1);
            }
        }
        else
            res++;

    return res;
}

//int main()
//{
//    vector<int> v = { 1,1,3,3,1,1,2,2,3,1,3,2 };
//    /*cout << minimumSum(v);*/
//
//    cout << minGroupsForValidAssignment(v);
//    return 0;
//}

int maxSatisfaction(vector<int>& s) {
    int n = s.size();
    sort(s.begin(), s.end());
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            dp[i][j] = dp[i - 1][j - 1] + s[i - 1] * j;
        }
    }

    int res = 0;
    for (int i = 0; i <= n; i++)
    {
        res = max(res, dp[n][i]);
    }
    return res;
}

int main()
{
    vector<int> v = { 4,3,2 };
    cout << maxSatisfaction(v);
    return 0;
}